1. Field of the Invention
This invention relates to digital signal processing systems employing binary multiplication and in particular to a binary multiplication means incorporating a modified Booth algorithm.
2. Description of the Prior Art
Binary multiplication is generally used in digital signal and data processing systems to perform high speed multiplication. The signal and data processing systems are presently formed with multiplier arrays on semiconductor or silicon chips preferably using CMOS technology. When operating a digital multiplier, along multiplication process is followed. For every digit in one of the factors (the multiplier) a multiple is formed of the other factor (the multiplicand) and is added to a running total (the partial product). If the whole operation is done simultaneously by fast multiplier, then one adder is needed for every digit in the multiplier.
The Booth algorithm is generally used to reduce by half the number of full adders required to perform a multiplication in an n x n bit array, having an x multiplicand of n bits and a y multiplier of n bits. Parallel binary multiplication implementing the Booth algorithm generates n partial products simultaneously and the partial products are added to form a final product of 2n bits.
The Booth algorithm is a procedure for multiplying two's complement numbers. However, the Booth algorithm does not present significant speed advantages. Therefore, the modified Booth algorithm is typically used in digital binary multiplication. With the modified Booth algorithm, to multiply using 2 bits of the multiplier at a time, it is necessary to look at 3 bits at a time, i.e., the current group of 2 bits and the most significant bit in the group which was looked at during the preceding cycle. Each multiplier is divided into substrings of 3 bits, with adjacent groups sharing a common bit. The modified Booth algorithm can be used with either unsigned or two's complement numbers, and requires that the multiplier be padded with a zero to the right of the least significant bit of the multiplier. When using the algorithm with unsigned numbers, it is necessary to pad the n bit multiplier with one or two zeroes to the left o the most significant bit.
The modified Booth algorithm generates n/2 independent partial products always. The modified Booth method produces four partial products from an 8-bit signed multiplier. The modified Booth technique uses n/2-1 adder delays for two's complement multiplication When unsigned multiplication is performed with the modified Booth algorithm, an extra row of adders is needed for the one bit increase in precision, resulting in n/2 adder delays.
The following table illustrates the use of the modified Booth algorithm, wherein three multiplier bits are encoded:
TABLE I __________________________________________________________________________ Bit 2.sup.1 2.sup.0 2.sup.-1 Yi + 1 Yi Yi - 1 Operation __________________________________________________________________________ 0 0 0 add zero (no string) +0 0 0 1 add multiplicand (end of string) +X 0 1 0 add multiplicand (a string) +X 0 1 1 add twice the multiplicand (end of string) +2X 1 0 0 subtract twice the multiplicand (beginning of -2Xing) 1 0 1 subtract the multiplicand (-2X and +X) -X 1 1 0 subtract the multiplicand (beginning of string) -X 1 1 1 subtract zero (center of string) -0 __________________________________________________________________________
A detailed explanation of binary multiplication and the operation of the modified Booth algorithm is presented in the textbook entitled "Introduction to Arithmetic for Digital Systems Designers", authored by Shlomo Waser, published by CBS College Publishing, Holt, Rinehart and Winston, 1982, see chapter 4, page 131, et seq. A further description of the operation of binary multipliers employing the Booth algorithm is provided in Monolithic Memories' Systems Design Handbook, Second Edition, published in 1984, pages 8-41 to 8-44.
A prior art modified Booth multiplier array for an 8-bit signed multiplier and an 8-bit signed multiplicand is illustrated in FIG. 1. The modified Booth multiplier array is comprised of four rows 10, 20, 30, 40 of Booth multiplexer and full adder cells. Each Booth multiplexer and full adder, a cell of the array, is represented by a box in FIG. 1. For example, the Booth multiplexer and adder cells 1MA1-1MA8 comprise the first row 10 of the array. The line 100 is connected to the Booth multiplexer and adder cells 1MA1, 2MA1, 3MA1, 4MA1. The line 10X0 is connected to the Booth multiplexer and full adder cells 1MA1, 1MA2, 2MA1, 2MA2, 3MA1, 3MA2, 4MA1, and 4MA2. The remaining lines 10Xl-10X7 are connected to the cells in a manner similar to that described for the line 10X0. The dashed lines in FIG. 1 represent the lines which have the carry signal from the full adder in each cell, while the solid lines represent the lines which have the sum signal from the full adder in each cell. The dotted lines represent the lines which have the sum and carry signals that are processed to form the bits of the product. Typically, the dotted lines are connected to a carry look ahead adder which performs the combinations necessary to define the final bits in the product. The control lines to the multiplexer in each cell of the array are not shown in FIG. 1 for clarity.
The Booth multiplexer and full adder cell in FIG. 1 is shown in more detail in FIG. 2. Each cell is comprised of a Booth multiplexer 201 and a full adder 200. The multiplexer 201 has seven input terminals 210-216. The terminal 210 is a first data input terminal and a line which provides the x.sub.i bit of the multiplicand is typically connected to it. The terminal 211 is a second data input terminal and a line which carries the x.sub.i-1 bit of the multiplicand is connected to it. The terminals 212-216 are input terminals for the multiplexer control lines. The output terminal 217 of the multiplexer 201 is connected to a first input terminal 218 of the full adder 200. The full adder has two additional input terminals 219, 220. The line connected to the terminal 219 provides a carry signal from a full adder in the previous row of the array, and so this terminal is called the "carry in" terminal. Similarly, the line connected to the terminal 220 provides a sum signal from a full adder in the previous row of the array, and so this terminal 220 is called the "sum in" terminal. A first output terminal 230 of the full adder 200 supplies the carry signal from the full adder 200 and a second output terminal 231 provides the sum signal. The terminal 230 will be referred to as the "carry out" terminal and the terminal 231 as the "sum out" terminal.
For the modified Booth algorithm in Table I, the control lines connected to the terminals 212-216 of the multiplexer 201 carry signals which correspond to the five possible results given in the last column of the table. Based upon he signals on the control lines, the multiplexer 201 will perform the correct operation on either the input signal corresponding to the x.sub.i bit of the multiplicand on the terminal 210 or the input signal corresponding to the x.sub.i-1 bit of the multiplicand on the terminal 211, and provide the resulting signal to the output terminal 217.
Another approach to binary multiplication employs a carry save technique, wherein a carry digit is produced as a result of an arithmetic operation on one digit place of two or more numbers when the sum of the two digits in the same digit place equals or exceeds the base of the number system in use. The resultant of the summation is transferred or carried over to the next higher digit place. For n bit operands the carry save technique requires n-1 adder delays in the array section of the multiplier.
A partial segment of a carry save multiplier array is shown in FIG. 3. Each of the circles in FIG. 3 represents a full adder with a logical AND gate. The dotted lines represent the carry signals from the adder while the solid lines are the sum signals.
A modified array technique of binary multiplication employs the carry save array wherein the sum and carry products skip every alternate row. The skip a row method increases the parallelism of the array and decreases the total number of adder delays to n/2+1. The array consists of odd rows and even rows. Sum and carry signals generated by an odd row are transferred to the nex odd row, and the carry signals generated by an even row are concurrently transferred to the next even row. Two pairs of sum and carry signal streams are formed in the array in parallel. Thereafter, the sums of the odd and even rows are added to produce a final product. In this way, the modified array reduces the number of addition stages by approximately one half that of the conventional carry save adder method. The technique is described in the 1984 IEEE International Solid-State Circuits Conference publication at pages 92-93, of the paper presented by Jun Iwamura et al., entitled "A CMOS/SOS Multilier".
The skip a row multiplier array could be implemented so as to use the modified Booth algorithm. However, the skip a row modified Booth multiplier array loses many of the advantages of the modified Booth multiplier array as shown in FIG. 1. For an nxn array, the first n/2-2 rows have seven un-added output terms and the last two rows have all the output terms un-added. Thus, the formation of the final sum and carry outputs requires considerable reduction. In addition, the seven un-added terms in the first n/2-2 rows do not easily combine in the minimum number of adder delays to provide the least significant bits of the product. The physical implementation is complex because straightening out the array requires each sum term to skip a row of adders and shift over four places while each carry term must skip a row of adders and shift over three places.
Thus, the prior art teaches either a uniform modified Booth array with n/2 adder delays, or a skip a row modified Booth array, which is complex and requires considerable signal reduction, with some improvement in speed. The present invention maintains the advantages of the modified Booth array, uniform physical implementation and easy reduction of the least significant bits of the product, and provides a significant increase in performance.